import java.util.ArrayDeque;
import java.util.Deque;

/**
* @description: 1475. 商品折扣后的最终价格
* @author hewei
* @date 2022/9/1 14:19
* @version 1.0
*/

public class FinalPrices {

    public int[] finalPrices(int[] prices) {
        int[] ans = new int[prices.length];
        System.arraycopy(prices, 0, ans, 0, prices.length);
        for (int i = 0; i < prices.length; i++) {
            ans[i] = prices[i];
        }
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                Integer pop = stack.pop();
                ans[pop] = prices[pop] - prices[i];
            }
            stack.push(i);
        }
        return ans;
    }
}
